package main.Q201_300;

import java.util.Arrays;

public class Q271_280 {
    public static void main(String[] args) {
        System.out.println("Question271：");
        System.out.println("Question272：");
        System.out.println("Question273：");
        System.out.println("Question274：H指数");
        System.out.println("Question275：H指数Ⅱ");
        System.out.println("Question276：");
        System.out.println("Question277：");
        System.out.println("Question278：第一个错误的版本");
        System.out.println("Question279：完全平方数");
        System.out.println("Question280：");
    }
}

class Question274{
    public int hIndex(int[] citations) {
        int result=0,length= citations.length;
        Arrays.sort(citations);
        for (int i=0;i< length;i++){
            if (length-i>=citations[i]) result=citations[i];
        }
        return result;
    }
}

class Question275{
    public int hIndex(int[] citations) {
        int n = citations.length,l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(citations, mid)) l = mid;
            else r = mid - 1;
        }
        return r;
    }
    public boolean check(int[] citations, int mid) {
        int index= citations.length-mid;
        if (citations[index]>=mid) return true;
        return false;
    }
}

class Question278{
    public int firstBadVersion(int n) {
        int left = 1, right = n;
//        while (left < right) { // 循环直至区间左右端点相同
//            int mid = left + (right - left) / 2; // 防止计算时溢出
//            if (isBadVersion(mid)) {
//                right = mid; // 答案在区间 [left, mid] 中
//            } else {
//                left = mid + 1; // 答案在区间 [mid+1, right] 中
//            }
//        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
}

class Question279{
    public int numSquares(int n) {
        int[] dp=new int[n+1];
        for (int i=1;i<=n;i++){
            int min=Integer.MAX_VALUE;
            for (int j=1;j*j<=i;j++) min=Math.min(min,dp[i-j*j]);
            dp[i]=min+1;
        }
        return dp[n];
    }
}